public class BinaryTree {
    //定义节点类
     class TreeNode{
         public char val;
         public TreeNode left;
         public TreeNode right;
         public TreeNode(char val){
             this.val=val;
         }
     }
     public TreeNode createTree(){
         TreeNode A=new TreeNode('A');
         TreeNode B=new TreeNode('B');
         TreeNode C=new TreeNode('C');
         TreeNode D=new TreeNode('D');
         TreeNode E=new TreeNode('E');
         TreeNode F=new TreeNode('F');
         TreeNode G=new TreeNode('G');
         TreeNode H=new TreeNode('H');
         A.left=B;
         A.right=C;
         B.left=D;
         B.right=E;
         E.right=H;
         C.left=F;
         C.right=G;
         return A;
     }
     //前序遍历
     public void preOder(TreeNode T){
         if(T==null){
             return ;
         }
         System.out.print(T.val+" ");
         preOder(T.left);
         preOder(T.right);
     }
    //中序遍历
    public void Oder(TreeNode T){
        if(T==null){
            return ;
        }
        Oder(T.left);
        System.out.print(T.val+" ");
        Oder(T.right);
    }
    //后序遍历
    public void postOder(TreeNode T){
        if(T==null){
            return ;
        }
        postOder(T.left);
        postOder(T.right);
        System.out.print(T.val+" ");
    }
    //获取树中结点的个数
    public int size(TreeNode T){
         if(T==null){
             return 0;
         }
         return size(T.left)+size(T.right)+1;//递归：左子树+右子树+根结点
    }
    //获取叶子结点个数
    public int getLeafNodeCount(TreeNode T){
         if(T==null){
             return 0;
         }
         if (T.left==null&&T.right==null){
             return 1;
         }
         int Left=getLeafNodeCount(T.left);//左边叶子节点数
         int Rigeht=getLeafNodeCount(T.right);//右边叶子节点数
         return Left+Rigeht;
    }

    //获取第K层结点的个数
    public int getKNodeCount(TreeNode T,int K){
         if (T==null){
             return 0;
         }
         if (K==1){
             return 1;
         }
         int Left=getKNodeCount(T.left,K-1);
         int Right=getKNodeCount(T.right,K-1);
        return Left+Right;
    }
    //获取二叉树的高度
    public int getHeight(TreeNode T){
         if(T==null){
             return 0;
         }
         int Left=getHeight(T.left);
         int Right=getHeight(T.right);
         if(Left>Right){
             return Left+1;
         }else {
             return Right+1;
         }
    }
    //检测值为value的值是否存在
    public TreeNode find(TreeNode T,char val){
         //判断是否为空
         if (T==null){
             return null;
         }
         //判断根结点是否为要找的值
         if (T.val==val){
             return T;
         }
         //判断左子树是否能找到
        TreeNode Left=find(T.left,val);
         if (Left!=null){
             return Left;
         }
         //判断右子树是否能找到
         TreeNode Right=find(T.left,val);
        if (Right!=null){
            return Right;
        }
        return null;
    }
}
